﻿using System;
using System.Collections.Generic;


namespace QSharp.Scheme.Classical.Sequential
{
    public static class QuickSort
    {
        /**
        * <summary>
        *  This implementation of quick sort split uses
        *  the first item as the pivot
        *  Quick sort is not stable
        * </summary>
        */
        public static int Split<T>(IList<T> list, int begin, int end, Comparison<T> compare)
        {
            int i = begin + 1;
            int j = i;
            T h = list[begin];

            for(; j < end; j++)
            {
                if(compare(list[j], h) >= 0) continue;
                T tmp = list[i];
                list[i] = list[j];
                list[j] = tmp;
                i++;
            }

            i--;
            if(i > begin)
            {
                list[begin] = list[i];
                list[i] = h;
            }
            return i;
        }

        public static void Sort<T>(IList<T> list, Comparison<T> compare)
        {
            Stack<int> segstk = new Stack<int>();
            segstk.Push(0);
            segstk.Push(list.Count);

            while(segstk.Count > 0)
            {
                int end = segstk.Pop();
                int begin = segstk.Pop();
                if(end <= begin + 1) continue;
                int s = Split(list, begin, end, compare);
                if(s > begin + 1)
                {
                    segstk.Push(begin);
                    segstk.Push(s);
                }
                if(end <= s + 2) continue;
                segstk.Push(s + 1);
                segstk.Push(end);
            }
        }

        public static void Sort<T>(IList<T> list) where T : IComparable<T>
        {
            Stack<int> segstk = new Stack<int>();
            segstk.Push(0);
            segstk.Push(list.Count);

            while(segstk.Count > 0)
            {
                int end = segstk.Pop();
                int begin = segstk.Pop();
                if(end <= begin + 1) continue;
                int s = Split(list, begin, end, (a, b) => a.CompareTo(b));
                if(s > begin + 1)
                {
                    segstk.Push(begin);
                    segstk.Push(s);
                }
                if(end <= s + 2) continue;
                segstk.Push(s + 1);
                segstk.Push(end);
            }
        }
    }
}
